package com.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 二叉树层次遍历
 * @date 2022/8/22 10:04
 */
public class levelTraversal {

    /**
     * Definition for a binary tree node.
     * **/
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null){
            return res;
        }
        trackBack(root,0);
        return res;
    }

    private void trackBack(TreeNode root, int index) {
        if(root!=null){
            List<Integer> list;
            if(res.size()<index+1){
                list=new ArrayList<>();
                res.add(list);
            }else {
                list = res.get(index);
            }
            list.add(root.val);
            trackBack(root.left,index+1);
            trackBack(root.right,index+1);
        }
    }
}
